package leetcode.editor.offer;

// 剑指 Offer 46. 把数字翻译成字符串
// https://leetcode.cn/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/
class BaShuZiFanYiChengZiFuChuanLcof {
    public static void main(String[] args) {
        Solution solution = new BaShuZiFanYiChengZiFuChuanLcof().new Solution();
        solution.translateNum(288);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 常规dp，空间复杂度较大
        /*public int translateNum(int num) {
            if (num < 10) {
                return 1;
            }
            String str = Integer.toString(num);

            // 含义：表示i为下标的数，总共有dp[i]种方式
            int[] dp = new int[str.length()];
            dp[0] = 1;
            int parseInt = Integer.parseInt(str.substring(0, 2));
            if (parseInt <= 25  && parseInt >= 10) {
                dp[1] = 2;
            } else {
                dp[1] = 1;
            }

            for (int i = 2; i < str.length(); i++) {
                int parseInt1 = Integer.parseInt(str.substring(i - 1, i + 1));
                if (parseInt1 <= 25 && parseInt1 >= 10) {
                    dp[i] = dp[i - 2] + dp[i - 1];
                } else dp[i] = dp[i - 1];
            }

            return dp[str.length() - 1];
        }*/

        // 使用字符串
        /*public int translateNum(int num) {
            String str = String.valueOf(num);

            int a = 1, b = 1;
            for (int i = 2; i <= str.length(); i++) {
                String substring = str.substring(i - 2, i);
                int c = substring.compareTo("25") <= 0 && substring.compareTo("10") >= 0 ? a + b : a;
                b= a;
                a = c;
            }

            return a;
        }*/

        // 由于计算是对称的，所以从后往前遍历都是一样的
        /*public int translateNum(int num) {
            String str = String.valueOf(num);

            int a = 1, b = 1;
            for (int i = str.length() - 1; i >= 0; i++) {
                String substring = str.substring(i, i + 2);
                int c = substring.compareTo("25") <= 0 && substring.compareTo("10") >= 0 ? a + b : a;
                b = a;
                a = c;
            }

            return a;
        }*/

        // 使用数字求余，字符串都不用开辟空间
        public int translateNum(int num) {
            int a = 1, b = 1, x, y = num % 10;
            while (num > 9) {
                num = num / 10;
                x = num % 10;
                int temp = 10 * x + y;
                int c = temp >= 10 && temp <= 25 ? a + b : a;
                b = a;
                a = c;
                y = x;
            }

            return a;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
